package org.example.code.test2024.eleven;

import java.util.*;

/**
 * @Title: test1120
 * @Author yxy
 * @Package org.example.code.eleven
 * @Date 2024/11/20 11:56
 * @description:
 */
public class test1120 {

    public int lengthOfLIS(int[] nums) {
       int[] dp = new int[nums.length];
       Arrays.fill(dp, 1);
       for(int i=1;i<nums.length;i++){
           for(int j=i-1;j>=0;j--){
               if(nums[i]>nums[j]){
                   dp[i] = Math.max(dp[i],dp[j]+1);
               }
           }
       }
       Arrays.sort(dp);
      return dp[dp.length-1];
    }


    /**
     * ["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int max = 0;
        int[] heights = new int[cols];
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(matrix[i][j]=='1'){
                    heights[j]=heights[j]+1;
                }else{
                    heights[j]=0;
                }
            }
            max = Math.max(max,fun(heights));
        }
        return max;
    }

    private int fun(int[] h) {
        int max = 0;
        int[] heights = new int[h.length+2];
        System.arraycopy(h, 0, heights, 1, h.length);
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<heights.length;i++){
           while(!stack.isEmpty() && heights[i]<heights[stack.peek()]){
               int height = heights[stack.pop()];
               int width = i-stack.peek()-1;
               max=Math.max(max,height*width);
           }
           stack.push(i);
        }
        return max;
    }




    public static void main(String[] args) {
        test1120 test = new test1120();
        char[][] num = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        char[][] n = {{'1','0'}};
        System.out.println(test.maximalRectangle(num));
    }
}
